package C035;

import org.w3c.dom.Node;

import java.rmi.Naming;
import java.util.HashMap;

/**
 * ClassName: C02
 * Package: C035
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/1/7 21:16
 * @Version 1.0
 * @Since 1.0
 */
public class C02 {
    public static void main(String[] args) {

    }

    static class LRUCache {
        class Node {
            int key;
            int val;
            Node last;
            Node next;

            public Node(int key, int val) {
                this.key = key;
                this.val = val;
            }
        }

        class DoubleLinkedList {
            Node head;
            Node tail;

            /**
             * @param node
             */
            public void moveToTail(Node node) {
                if (node == null) {
                    return;
                }
                if (tail == node) {
                    return;
                }
                // 如果是头节点
                if (head == node) {
                    head = head.next;
                    if (head != null) { // 如果元素只有一个的话, 避免NULL异常
                        head.last = null;
                    } else {
                        tail = null;
                    }
                } else {
                    // 中间节点
                    node.last.next = node.next;
                    node.next.last = node.last;
                }
                tail.next = node;
                node.last = tail;
                node.next = null;
                tail = node;
            }

            // 增加元素
            public void add(Node node) {
                if (node == null) {
                    return;
                }

                // 如果链表为null
                if (head == null) {
                    head = node;
                    tail = node;
                    return;
                }
                // 正常链表
                tail.next = node;
                node.last = tail;
                tail = node;
            }

            /**
             * 溢出头元素
             *
             * @return
             */
            public Node remove() {
                if (head == null) {
                    return null;
                }
                Node res = head;
                head = head.next;
                if (head != null) {
                    head.last = null;
                } else {
                    tail = null;
                }
                return res;
            }
        }


        HashMap<Integer, Node> map = new HashMap<>();
        int capacity;
        DoubleLinkedList list = new DoubleLinkedList();

        public LRUCache(int capacity) {
            this.capacity = capacity;
        }


        /**
         * 增加元素
         * @param k
         * @param v
         */
        public void put(int k, int v) {
            if (map.containsKey(k)) {
                // 修改元素
                Node node = map.get(k);
                node.val = v;
                // 修改元素的双向链表的位置
                list.moveToTail(node);
            }else {
                // 如果容量不足
                if(map.size() == capacity) {
                    Node node = list.remove();
                    map.remove(node.key);
                }
                // 增加元素
                Node node = new Node(k, v);
                map.put(k, node);
                list.add(node);
            }
        }


        public int get(int k) {
            if (map.containsKey(k)) {
                Node node = map.get(k);
                // 调整node的双向链表的位置
                list.moveToTail(node);
                return node.val;
            }else {
                return -1;
            }
        }
    }

}
